
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1605. -- [Usaco2008 Open]Crisis on the Farm
</title><center><h2>1605: [Usaco2008 Open]Crisis on the Farm
</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>96&nbsp;&nbsp;<span class=green>Solved: </span>38<br>[<a href='submitpage.php?id=1605'>Submit</a>][<a href='problemstatus.php?id=1605'>Status</a>][<a href='bbs.php?id=1605'>Discuss</a>]</center><h2>Description</h2><div class=content>Farmer John and his herd of exotic dancing bovines have been 
practicing for his new moosical, "The Street Cow Named Desire". At 
one point in the middle of rehearsal, his cows are stacked on top 
of each other in N (1 <= N <= 1,000) sets of 30, one cow standing 
on the back of the other (they are quite amazing cows). Thus, the 
pasture is dotted with both these stacks of 30 cows and also, in 
separate locations, M (1 <= M <= 1,000) haystacks. Below is a sample 
of one way they might be laid out: 

8 ......... 
7 ....CH.H. C = stack of 30 cows 
6 ......... 
5 ......... H = haystack 
4 ..C.HH... 
3 ......... 
2 .....C.HH 
1 ......... 
123456789 

As the musical's conductor, Farmer John has four whistles with 
various tones. One whistle commands the cow at the bottom of each 
stack to move (along with all the stacked cows) one unit north, 
another indicates a move to the south, one indicates a move to the 
east, and a fourth to order a move to the west. 

Any time the stack of cows enters a grid location with a haystack, 
the cow on the top of the stack (even if the stack has height one) 
will jump onto the haystack while the remaining cows move into the 
same location as the haystack. Thus, if the bottom cow encounters 
30 haystacks (perhaps different haystacks, perhaps not), the stack 
of 30 cows is exhausted with all the cows standing on top of haystacks 
(or standing on cows on haystacks). The sturdy haystacks can each 
support an unlimited number of cows. 

Farmer John glances across his pasture to Farmer Don's milking 
facility to see, to his horror, a huge milk tank exploding and 
unleashing a giant tidal wave of milk making its way toward the 
performing cows! Since any cows on a haystack are safe, FJ must now 
do what he can to save the lives of as many cows as possible using 
what has turned from a simple dance routine into a lifesaving 
technique. 

Given the number of times K (1 <= K <= 30) farmer John can blow a 
whistle until the wave of milk crashes over the pasture and also 
the X_i, Y_i positions (1 <= X_i <= 1,000; 1 <= Y_i <= 1,000) of 
the N stacks of cows and M haystacks (none of which currently has 
any cows on it), report the greatest number of cows that can be 
saved and find a sequence of whistle blows that does the job. The 
sequence should be reported in terms of the four directions, 'E' 
for east, 'N' for north, 'W' for west, 'S' for south. Among all 
such sequences, farmer John wants the lexicographically least. 
Initial locations of cows and haystacks will not share the same 
coordinates in the input file. 

Cows can be moved to any location, including ones outside the 
pasture. 
John有N摞高度为30的牛,N摞的牛看成一个整体，要移动的时候一起移动. 
将移动到草堆所在的位置时，最上面那个牛就会跳到草堆上去. 
现在给出M个草堆所在的位置，以及移动的次数K（K小于30) 
问最多可移动多少头牛到草堆上去,并输出你每次移动的方向 



</div><h2>Input</h2><div class=content>* Line 1: Three space-separated integers: N, M, and K 
* Lines 2..N+1: Line i+1 describes the X,Y location of a stack of 30 
cows using two space-separated integers: X_i and Y_i 
* Lines N+2..N+M+1: Line i+N+1 describes the X,Y location of a 
haystack using two space-separated integers: X_i and Y_i 
</div><h2>Output</h2><div class=content>
* Line 1: A single integer that is the most number of cows that can be
        saved.
* Line 2: K characters, the lexicographically least sequence of
        commands FJ should issue to maximize the number of cows saved.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 6 3 <br />
3 4 <br />
6 2 <br />
5 7 <br />
8 2 <br />
9 2 <br />
6 4 <br />
5 4 <br />
6 7 <br />
8 7 <br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>Use the 'east' whistle three times, at which point the milk floods<br />
the area.  Each haystack ends up saving 1 cow.<br />
<br />
6 <br />
EEE <br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1605'>Submit</a>][<a href='problemstatus.php?id=1605'>Status</a>][<a href='bbs.php?id=1605'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
